This invention generally relates to determining which of a plurality of peer entities in a data processing system has access to a common resource. More particularly it relates to determining the winner of a race to a system privilege in a distributed system.
There are many prior art techniques for determining which of a plurality of processors or associated processes is allowed access to and/or controls a particular common resource or a system process in a data processing system. The data processing system may be a standalone system or may comprise several separate data processing systems coupled together by a network to form a distributed data processing system. Many of these prior art techniques rely on establishing the relative priority of the contending processors or processes, for example, allowing a higher priority processor to override a lower priority processor. In other prior art, messages pass a token through the network, whichever system holds the token is allowed access to and control of the network or the resource.
The present invention proposes that a simpler and more equitable rule would be to allow the first peer processor or peer process to attempt access to the resource to become the resource master. In a distributed system where the processors and processes are essentially identical, it would appear to be no overriding reason to give a particular processor or process higher priority over any of its identical peers.
However, in a distributed system, events happen in a truly concurrent manner. It is very difficult to know which processor or process was the first to attempt access to a common resource or perform a given action. There is no unique reference point from which the distributed system can reliably establish the first processor.
In a single processor system where all processes can be timed stamped by the internal clock and there is a shared memory, it is relatively easy to establish the first process to attempt a given action. However, in a distributed system, the internal clocks may vary by several, seconds, being set by an individual user or system administrator. Even if the clocks are set correctly at the beginning, the clocks still drift as time progresses. The determination of which peer was first is dependent upon millisecond precision; the use of internal clocks is not adequate.
Often distributed programs rely on having a master or coordinator process and several secondary or shadow processes. Although the processes are essentially identical, one of them is chosen as master and the rest are asked to play the secondary shadow roles. A process which is just coming up must know whether it is the master process or a secondary shadow. Since in a distributed system a process cannot look at the other systems' memories, it is not possible to know whether this new process is the master. A name service might be used to locate a master process, however, unless the name service allows atomic registration of master processes, it becomes possible for multiple processes to register as master at the same time.
The present invention provides a solution to the problem of determining which processor or process is first to attempt to gain control of a common resource or privilege, particularly in a distributed system.